package assignment;

public class Demo {
    public final static int INFINITY=Integer.MAX_VALUE;
    public static void main(String[] args)throws Exception {
        Object vexs[]={"A","B","E","G"};
        int[][] arcs={{0,INFINITY,INFINITY,10},
                      {INFINITY,0,4,INFINITY},
                      {INFINITY,4,0,8},
                      {10,INFINITY,8,0}};
        MGraph G=new MGraph(GraphKind.UDG,4,3,vexs,arcs);
        ShortestPath_FLOYD floyd=new ShortestPath_FLOYD();
        floyd.floyd(G);
        display(floyd.getD());
        findPlace(G,floyd.getD());
    }
    public static void display(int[][] D){
        System.out.println("各单位之间的最短路径长度为：");
        for(int v=0;v<D.length;v++){
            for(int w=0;w<D.length;w++)
                System.out.print(D[v][w]+"\t");
            System.out.println();
        }
    }
    public static void findPlace(MGraph G,int[][] D)throws Exception{
        int min=INFINITY;
        int sum=0;
        int u=-1;
        for(int v=0;v<D.length;v++){
            sum=0;
            for(int w=0;w<D.length;w++)
                sum+=D[v][w];
            if(min>sum){
                min=sum;
                u=v;
            }
        }   
        System.out.println("超市应设在"+G.getVex(u)+"单位，其到各单位的路径长度依次为：");
        for(int i=0;i<D.length;i++)
            System.out.print(D[u][i]+"\t");
        System.out.println();
    }
    public void print() {
        System.out.print("最佳路径为：");
        System.out.print("P-->E");
    }
}
